#include "QuadTree.h"

QuadTree::QuadTree(int width, int height)
{
	_widthMap = width;
	_heightMap = height;
	_root = new QuadNode(0,0,width, height);
}
void QuadTree::AddObj(QuadNode *root, Object *obj)
{
	// size of obj
	int widthOfObject = obj->_pRECT->right - obj->_pRECT->left;
	int heightOfObject = obj->_pRECT->bottom - obj->_pRECT->top;
	
	// size of root
	int widthOfRoot = _root->_rect->right - _root->_rect->left;
	int heightOfRoot = _root->_rect->bottom - _root->_rect->top;

	// line divide root to 4 pices
	// thang dung
	int vertical = (_root->_rect->right + _root->_rect->left) / 2;
	// nam ngang
	int horizontal = (_root->_rect->bottom + _root->_rect->top) / 2;

	// add root if obf not belong 1 in 4 pices
	int caseToAdd = 0;
	if ((widthOfObject*heightOfRoot > widthOfRoot*heightOfRoot / 4 ) || (obj->_pRECT->left <= vertical && obj->_pRECT->right >= vertical) || (obj->_pRECT->top <= horizontal && obj->_pRECT->bottom >= horizontal))
	{
		caseToAdd = 0;
	}
	else if(obj->_pRECT->left >= _root->_rect->left  &&  obj->_pRECT->right <= vertical  &&  obj->_pRECT->top >= _root->_rect->top  &&  obj->_pRECT->bottom <= horizontal)
	{
	// add left top 
		caseToAdd = 1;
	}
	else if(obj->_pRECT->left >= vertical  &&  obj->_pRECT->right <= _root->_rect->right  &&  obj->_pRECT->top <= _root->_rect->top  &&  obj->_pRECT->bottom >= horizontal)
	{
		// add right top
		caseToAdd = 2;
	}
	else if(obj->_pRECT->left >= _root->_rect->left  && obj->_pRECT->right <= vertical  && obj->_pRECT->top <= horizontal  && obj->_pRECT->bottom >= _root->_rect->bottom)
	{
		// add left bottom
		caseToAdd = 3;
	}
	// add right bottom
	else caseToAdd = 4;

	if(caseToAdd == 0)
	{
		_root->listOfObject.push_back(obj);// becase "de quy" so prorame alway add obj here
	}
	else if(widthOfRoot/2 > LIM_W_H && heightOfRoot/2)
	{
		switch (caseToAdd)
		{
		case 1: 
			{
				if(_root->_leftTop == NULL)
					_root->_leftTop = new QuadNode(_root->_rect->left, _root->_rect->top,widthOfRoot/2, heightOfRoot/2);
				AddObj(_root->_leftTop,obj);
			}
			break;
		case 2:
			{
				if(_root->_rightTop == NULL)
					_root->_rightTop = new QuadNode(vertical, _root->_rect->top, widthOfRoot/2, heightOfRoot/2);
				AddObj(_root->_rightTop, obj);
			}
			break;
		case 3:
			{
				if(_root->_leftButton == NULL)
					_root->_leftButton = new QuadNode(_root->_rect->left , horizontal , widthOfRoot/2, heightOfRoot/2);
				AddObj(_root->_leftButton,obj);
			}
			break;
		case 4:
			{
				if(_root->_rightButtom == NULL)
					_root->_rightButtom = new QuadNode(vertical, horizontal,widthOfRoot/2, heightOfRoot/2);
				AddObj(_root->_rightButtom,obj);
			}
		}
	}

}
bool QuadTree::CheckCircleInCircle(Circle circle1 , Circle circle2)
{
	double tam = ((circle1._x * circle1._x)+(circle2._x * circle2._x))  * 	((circle1._y * circle1._y)+(circle2._y * circle2._y));
	double distancecenter = sqrt(tam);
	if(circle1._r + circle2._r <= distancecenter)
		return true;	
	return false;
}
bool QuadTree::CheckRectInRect(RECT rect1, RECT rect2)
{
	if(CheckPointInRect(rect1.left, rect1.top,rect2) || CheckPointInRect(rect1.right, rect1.top,rect2) ||
		CheckPointInRect(rect1.left, rect1.bottom,rect2)  || CheckPointInRect(rect1.right, rect1.top,rect2))
		return true;
	return false;
}
bool QuadTree::CheckPointInRect(int x, int y, RECT rect)
{
	if(x >= rect.left && x <= rect.right && y>= rect.top && y<=rect.bottom)
		return true;
	return false;
}
void QuadTree::CheckCollision(QuadNode *root, RECT rect,Circle circle, int Id,vector<Object*>result)
{
	
	for(int i = 0; i < root->listOfObject.size() ; i++)
	{
		if(root->listOfObject[i]->_typeObj != -1)
			if(root->listOfObject[i]->_status != 2)
				if(root->listOfObject[i]->_id != Id)
					if(CheckCircleInCircle(*root->listOfObject[i]->_Pcircle,circle))
						if(CheckRectInRect(*root->listOfObject[i]->_pRECT,rect))
						{
							result.push_back(root->listOfObject[i]);
						}
	}
	if(root->_leftTop != NULL && CheckRectInRect(*root->_leftTop->_rect,rect) )
	{
		CheckCollision(root->_leftTop,rect,circle,Id,result);
	}
	if(root->_leftButton != NULL && CheckRectInRect(*root->_leftButton->_rect,rect))
	{
		CheckCollision(root->_leftButton,rect,circle,Id,result);
	}
	if(root->_rightTop != NULL && CheckRectInRect(*root->_rightTop->_rect,rect))
	{
		CheckCollision(root->_rightTop,rect,circle,Id,result);
	}
	if(root->_rightButtom != NULL && CheckRectInRect(*root->_rightButtom->_rect,rect))
	{
		CheckCollision(root->_rightButtom,rect,circle,Id,result);
	}
}
void QuadTree::GetAllObjInRect(QuadNode *root ,RECT rect , Circle circle ,vector<Object *> result)
{
	for (int i=0 ; i< root->listOfObject.size() ; i++)
	{
		if(root->listOfObject[i]->_typeObj != -1 && root->listOfObject[i]->_status != 2)
		if (CheckCircleInCircle(*root->listOfObject[i]->_Pcircle , circle))
			if(CheckRectInRect(*root->listOfObject[i]->_pRECT ,rect) || CheckRectInRect(rect, *root->listOfObject[i]->_pRECT))
				result.push_back(root->listOfObject[i]);
	}
}